﻿#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


//⽤⼀个 cur 指针来扫描整个数组，另⼀个 dest指针⽤来记录非零数序列的最后⼀个位置。
//根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。
//在 cur 遍历期间，使[0, dest] 的元素全部都是非零元素，[dest + 1, cur - 1] 的元素全是零。
// 
//算法流程：
//a.初始化 cur = 0 （⽤来遍历数组）， dest = -1 
//b.cur 依次往后遍历每个元素，遍历到的元素会有下⾯两种情况：
//i.遇到的元素是 0 ， cur 直接 ++ 
// 因为我们的⽬标是让[dest + 1, cur - 1] 内的元素全都是零，
// 因此当 cur 遇到 0 的时候，直接 ++ ，就可以让 0 在 cur - 1的位置上，从⽽在[dest + 1, cur - 1] 内
//ii.遇到的元素不是 0 ， dest++ ，并且交换 cur 位置和 dest 位置的元素，之后让cur++ ，扫描下⼀个元素。
//• 因为 dest 指向的位置是⾮零元素区间的最后⼀个位置，如果扫描到⼀个新的非零元素，
// 那么它的位置应该在 dest + 1 的位置上，因此 dest 先⾃增 1 
//• dest++ 之后，指向的元素就是 0 元素（因为非零元素区间末尾的后⼀个元素就是0 ）
// 因此可以交换到 cur 所处的位置上，实现[0, dest] 的元素全部都是非零元素，[dest + 1, cur - 1] 的元素全是零。

class Solution {
public:
    void moveZeroes(vector<int>& nums)
    {
        int cur = 0, dest = -1;
        while (cur <= nums.size() - 1)
        {
            while (cur < nums.size() && nums[cur] == 0)
            {
                cur++;
            }
            if (cur < nums.size() && nums[cur] != 0)
            {
                swap(nums[cur++], nums[++dest]);
            }
        }
    }
};